---
title: "玩具蛇"
created: 2025-11-28
tags:
  - 算法
---

# 玩具蛇

## 题目 [玩具蛇](https://www.lanqiao.cn/paper/3839/problem/1022/)

![[image-2de0123e.png]]

## 思路分析

首先要做一遍全排列 问题是 怎么判断某个排列是否合法

存在图里面 然后遍历图 对图的每个位置往4方向拓展 看有没有相邻的数 如果没有则一定不合法？貌似可行 但有些太暴力了吧……

![[image-d8ff786e.png]]

结果半天不出来

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<int> a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int m[4][4];
bool st[4][4];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool isVaild(int x,int y){
	return x>=0 && x<=3 && y>=0 && y<=3;
}
void dfs(int x, int y, bool& flag) {
    if (!flag)
		return;

    int cnt = 0;
    for (int i=0;i<4;i++) {
        int nx=x+dx[i],ny=y+dy[i];
        if(isVaild(nx, ny)) {
            if(abs(m[nx][ny]-m[x][y])!=1)
				cnt++;
            if(abs(m[nx][ny]-m[x][y])==1 && !st[nx][ny]){
                st[nx][ny] = true;
                dfs(nx, ny, flag);
            }
        }
    }
    if(cnt == 4)
		flag=false;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	long long cnt=0;
	do{
		memset(st,false,sizeof st);
//		m[0][0]=a[0],m[0][1]=a[1],m[0][2]=a[2],m[0][3]=a[3];
//		m[1][0]=a[4],m[1][1]=a[5],m[1][2]=a[6],m[1][3]=a[7];
//		m[2][0]=a[8],m[2][1]=a[9],m[2][2]=a[10],m[2][3]=a[11];
//		m[3][0]=a[12],m[3][1]=a[13],m[3][2]=a[14],m[3][3]=a[15];
		for(int i=0;i<16;i++){
			m[i/4][i%4]=a[i];
		}

		bool flag = true;
		st[0][0] = true;
		dfs(0,0,flag);

		if(flag)
			cnt++;

	}while(next_permutation(a.begin(),a.end()));
	cout<<cnt;
	return 0;
 }
```

等等看吧 先写后面的

不行 几个小时都算不出来 得换个角度

从八皇后的角度来看 每个位置能不能放置

枚举每个位置 以它为起点 开始放蛇 若最后放满16个格子 就是一种合法方案

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int cnt;

bool st[4][4];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
  	return x>=0 && x<=3 && y>=0 && y<=3 && !st[x][y];
}

void dfs(int step,int x,int y){
	if(step==16){
		cnt++;
		return;
	}

	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(isVaild(nx,ny)){
      		st[nx][ny]=true;
		  	dfs(step+1,nx,ny);
		 	 st[nx][ny]=false;
   		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(int i=0;i<4;i++){	//对4x4的格子 枚举玩具蛇第一个步放置的所有可能
		for(int j=0;j<4;j++){
			st[i][j]=true;
			dfs(1,i,j);
			st[i][j]=false;
		}
	}
	cout<<cnt;
	return 0;
}
```

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[阶乘约数|阶乘约数]] 🏠 [[00-冲刺国赛]] ➡️ [[皮亚诺曲线距离|皮亚诺曲线距离]]